package leetcode.top100;

import leetcode.a_总结分布.Code09_单调栈问题;

import java.util.Arrays;
import java.util.Stack;

/**
 * 给定一个整数数组，你需要寻找一个连续的子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。
 * <p>
 * 你找到的子数组应是最短的，请输出它的长度。
 * <p>
 * 示例 1:
 * <p>
 * 输入: [2, 6, 4, 1, 10, 9, 15]
 * 输出: 6
 * 解释: 你只需要对 [2,6, 4, 1, 10, 9] 进行升序排序，那么整个表都会变为升序排序。
 * 说明 :
 * <p>
 * 输入的数组长度范围在 [1, 10,000]。
 * 输入的数组可能包含重复元素 ，所以升序的意思是<=。
 * <p>
 * <p>
 * 单调栈相关问题{@link Code09_单调栈问题}
 *
 * @date 2020/4/7 13:25
 */
public class Code581_最短无序连续子数组 {
    /**
     * 方式1：
     * 固定数组起点i，从i遍历到n。当i<j<n时，如果nums[j]< nums[i]，
     * 那么就记录至少要交换当前这两个位置。
     * 记录left = i,right = j。
     * 当遍历完所有i后，找到正确的i和j。
     */
    public int findUnsortedSubarray1(int[] nums) {
        if (nums == null || nums.length <= 1) return 0;
        int len = nums.length;
        int left = len - 1;
        int right = 0;
        for (int i = 0; i < len - 1; i++) {
            for (int j = i + 1; j < len; j++) {
                //非递增，则记录当前两个位置。至少要交换的区间是 j-i+1
                if (nums[j] < nums[i]) {
                    left = Math.min(left, i);
                    right = Math.max(right, j);
                }
            }
        }
        return right - left <= 0 ? 0 : right - left + 1;
    }

    /**
     * 方式2：基于排序。利用系统排序，然后遍历最左侧和最右侧第一个和原序列不同的位置。
     */
    private static int findUnsortedSubarray2(int[] nums) {
        if (nums == null || nums.length <= 1) return 0;
        int len = nums.length;
        int[] copy = Arrays.copyOf(nums, len);
        Arrays.sort(copy);
        int start = len - 1;
        int end = 0;
        for (int i = 0; i < len; i++) {
            if (copy[i] != nums[i]) {
                start = Math.min(i, start);
                end = Math.max(i, end);
            }
        }
        return end - start > 0 ? end - start + 1 : 0;
    }

    /**
     * 方式3：基于一种策略。
     * 拿[2, 6, 4, 1, 10, 9, 15]来说，
     * 从左到右遍历数组，找到第一个降序的位置，从元素4开始，找4到len最小元素，最后是1。
     * 注意一定要从4开始找到最后，找最小的。
     * 如1, 3, 5,4,2如果不找到最后记录的元素是4，而应该记录2.
     * <p>
     * 从右到左遍历，找到第一个升序的元素，从10开始，向前找最大的元素最后是10。
     * <p>
     * 从左遍历，找到第一个比min(也就是1)大的元素 是2,1应该属于这个位置，记录left = 0.
     * 从右遍历，找到第一个比10小的元素是9,10应该属于这个位置，记录right=5.
     * 返回结果。
     */

    private static int findUnsortedSubarray3(int[] nums) {
        if (nums == null || nums.length <= 1) return 0;
        boolean sorted = true;
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for (int i = 1; i < nums.length; i++) {
            //第一个失序位置
            if (nums[i] < nums[i - 1]) sorted = false;
            if (!sorted) min = Math.min(min, nums[i]);
        }
        if (sorted) return 0;
        sorted = true;
        for (int i = nums.length - 2; i >= 0; i--) {
            //找到第一个失序位置
            if (nums[i] > nums[i + 1]) sorted = false;
            if (!sorted) max = Math.max(max, nums[i]);
        }
        //从左找第一个比min大的位置，应该是min属于的位置
        //从右找第一个比max小的位置，应该是max属于的位置
        int left = 0;
        while (nums[left] <= min) left++;
        int right = nums.length - 1;
        while (nums[right] >= max) right--;
        return right > left ? right - left + 1 : 0;

    }

    /**
     * 方式4：思路同方式3，利用单调栈。
     * 先找到最左侧的位置： 利用单调递增栈（非递减）。
     * 若当前元素小于栈顶元素，说明失序，栈一直弹，直到比当前元素大。
     * 弹的过程中记录最左left。这就是要交换的最终位置。
     * 同理找最右位置
     */
    private static int findUnsortedSubarray4(int[] nums) {
        if (nums == null || nums.length <= 1) return 0;
        Stack<Integer> stack = new Stack<>();
        //左侧找left
        int left = nums.length - 1;
        for (int i = 0; i < nums.length; i++) {
            //失序。假设从 m -  i-1，都比nums[i]大，则找到m。至少是要交换的位置
            while (!stack.isEmpty() && nums[i] < nums[stack.peek()]) {
                left = Math.min(left, stack.pop());
            }
            stack.push(i);
        }
        //右侧找right
        int right = 0;
        for (int i = nums.length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
                right = Math.max(right, stack.pop());
            }
            stack.push(i);
        }
        return right > left ? right - left + 1 : 0;
    }

    public static void main(String[] args) {
        int[] arr = {2, 6, 4, 8, 10, 9, 15};
        System.out.println(findUnsortedSubarray3(arr));
    }
}
